import javax.swing.tree.TreeNode;
import java.util.*;
public class Solution {
    //1.两数之和(暴力)
    public int[] twoSum(int[] nums, int target) {

        int[] array = new int[2];
        int len = nums.length;
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                if(nums[i] + nums[j] == target){
                    array[0] = i;
                    array[1] = j;
                    break;
                }
            }
        }
        return array;
    }
/*    public int[] twoSum(int[] nums, int target) {
        //哈希表
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[2];
    }*/
    //2.盛最多水的容器(暴力，最后一个测试超时)
    public int maxArea(int[] height) {
        int max = -1;
        int len = height.length;
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                if((j - i) * Math.min(height[i], height[j]) > max){
                    max = (j - i) * Math.min(height[i], height[j]);
                }
            }
        }
        return max;
    }
    // 盛最多水的容器(模拟边界法)
/*    public int maxArea(int[] height) {
        //假设最大值
        int max = -1;
        //双指针，分别在两端点
        int left = 0;
        int right = height.length - 1;
        while(left < right){
            //先判断是否放入最大值
            if((right - left) * Math.min(height[left], height[right]) > max){
                max = (right - left) * Math.min(height[left], height[right]);
            }
            //总是移动高度较小的那个指针,若相等，随便一个就可以，这里移动left
            if(height[left] > height[right]){
                right--;
            }else{
                left++;
            }
        }
        return max;
    }*/
    //3.三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> array = new ArrayList<>();
        //整体先排序
        Arrays.sort(nums);
        int len = nums.length;
        //遍历最后三个数的时候停止
        for(int i = 0; i < len - 2; i++){
            //排好序的，这儿大于0，后面的肯定都大于0
            if(nums[i] > 0){
                break;
            }
            //去重
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            //i的右边用双指针法
            int left = i + 1;
            int right = len - 1;
            while(left < right){
                int sum = nums[left] + nums[right] + nums[i];
                //若和大于0，right就左移，减小和,顺便去重
                if(sum < 0){
                    while(left < right && nums[left] == nums[++left]);
                }else if(sum > 0){
                    while(left < right && nums[right] == nums[--right]);
                }else{
                    //找到了，放入表中
                    array.add(new ArrayList<Integer>(Arrays.asList(nums[left], nums[right], nums[i])));
                    //左右去重
                    while(left < right && nums[right] == nums[--right]);
                    while(left < right && nums[left] == nums[++left]);
                }
            }
        }
        return array;
    }
    //4.搜索插入位置
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(nums[i] >= target){
                return i;
            }
        }
        return len;
    }
    //5.加一
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        //若最低位不等于9，则可以直接给最低位加一返回
        if(digits[len - 1] != 9){
            digits[len - 1]++;
            return digits;
        }
        //到这里说明最低位是9
        //用一个指针，从后往前找，直到不是9为止，是9的统统改成0
        int end = len - 1;
        while(end >= 0){
            if(digits[end] == 9){
                digits[end] = 0;
                end--;
            }else{
                digits[end]++;
                return digits;
            }

        }
        //到了这里说明都是9,那么
        int[] retArr = new int[len + 1];
        retArr[0] = 1;
        return retArr;
    }
    //6.合并两个有序数组(时间复杂度高)
/*    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //把nums2直接加入到nums1的后面
        for(int i = m; i < m + n; i++){
            nums1[i] = nums2[i - m];
        }
        //整体排序
        Arrays.sort(nums1);
    }*/
    //6.合并两个有序数组(双指针，高效)
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //先放入一个新创建的数组
        int[] retArr = new int[m + n];
        //双指针发填充retArr数组
        int n1 = 0;
        int n2 = 0;
        //retArr的指针
        int ret = 0;
        while(n1 < m && n2 < n){
            if(nums1[n1] < nums2[n2]){
                retArr[ret++] = nums1[n1++];
            }else{
                retArr[ret++] = nums2[n2++];
            }
        }
        //剩下没放完的
        while(n1 < m){
            retArr[ret++] = nums1[n1++];
        }
        while(n2 < n){
            retArr[ret++] = nums2[n2++];
        }
        //覆盖nums1
        for(int i = 0; i < m + n; i++){
            nums1[i] = retArr[i];
        }
    }
    //7. 将有序数组转换为二叉搜索树
 /*   public TreeNode sortedArrayToBST(int[] nums) {
        return buildTreeNode(nums, 0, nums.length - 1);
    }*/
/*    private TreeNode buildTreeNode(int[] array, int left, int right){
        if(left > right){
            return null;
        }
        //由于是平衡的二叉搜索树，所以用中点来做根节点(这里的算法是为了防止溢出)
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(array[mid]);
        //左右递归建立平衡二叉搜索树
        root.left = buildTreeNode(array, left, mid - 1);
        root.right = buildTreeNode(array, mid + 1, right);
        return root;
    }*/

    //8.杨辉三角(一)
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> retList = new ArrayList<>();
        for(int i = 0; i < numRows; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                //添加1
                if(j == 0 || j == i){
                    list.add(1);
                }else{//直接赋值和
                    list.add(retList.get(i - 1).get(j - 1) + retList.get(i - 1).get(j));
                }
            }
            retList.add(list);
        }
        return retList;
    }
    //9.杨辉三角(二)
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> listKey = new ArrayList<>();
        for(int i = 0; i <= rowIndex; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    list.add(1);
                }else{
                    list.add(listKey.get(i - 1).get(j - 1) + listKey.get(i - 1).get(j));
                }
            }
            listKey.add(list);
        }
        return listKey.get(rowIndex);
    }
    //买卖股票的最佳时机(暴力，超时)
    public int maxProfit(int[] prices) {
        //暴力
        int max = -1;
        int len = prices.length;
        for(int i = 0; i < len; i++){
            for(int j = i; j < len; j++){
                if(prices[j] - prices[i] > max){
                    max = prices[j] - prices[i];
                }
            }
        }
        return max;
    }
    //买卖股票的最佳时机(动态规划)
    public int maxProfit(int[] prices) {
        //动态规划
        //遍历，先找出一个最小值，向后走，边走边计算最大利润，
        //如果还有更小的，就替换掉那个最小值
        int min = Integer.MAX_VALUE;
        int max = 0;
        int len = prices.length;
        for(int i = 0; i < len; i++){
            //先找到一个最小值
            if(min > prices[i]){
                min = prices[i];
            }else if(prices[i] - min > max){//计算最大利润
                max = prices[i] - min;
            }
        }
        return max;
    }
    //在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int[] retArr = new int[2];
        //设置初始值
        retArr[0] = -1;
        retArr[1] = -1;
        //二分查找法
        int left = 0;
        int right = nums.length - 1;
        //找目标值
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                //找到了，记录始末位置
                while(mid >= 0 && nums[mid] == target){
                    mid--;
                }
                //找到初始位置
                retArr[0] = ++mid;
                int len = nums.length;
                while(mid < len && nums[mid] == target){
                    mid++;
                }
                retArr[1] = --mid;
                return retArr;
            }
        }
        //没找到
        return retArr;
    }
}
